#include <math.h>

float graphNodeDistance(GraphNode * a, GraphNode * b)
{
	int dx = a->pos.x-b->pos.x;
	int dy = a->pos.y-b->pos.y;
	return sqrt((float)(dx*dx+dy*dy));
}
void makeConnections(TemplateVector<GraphNode> & nodes_out, float neighborDistance, bool mustHaveNeighbor)
{
	float dist, closestDist;
	int closestN = -1;
	GraphNode * node, * nodei;
	for(int n = 0; n < nodes_out.size(); ++n)
	{
		node = &nodes_out.get(n);
		closestN = -1;
		for(int i = 0; i < nodes_out.size(); ++i)
		{
			if(i != n)
			{
				nodei = &nodes_out.get(i);
				dist = graphNodeDistance(node,nodei);
				if(closestN < 0 || dist < closestDist)
				{
					closestN = i;
					closestDist = dist;
				}
				if(dist < neighborDistance)
				{
					node->connectTo(nodei, dist);
				}
			}
		}
		if(mustHaveNeighbor && closestDist > neighborDistance)
		{
			node->connectTo(&nodes_out.get(closestN), closestDist);
			nodes_out.get(closestN).connectTo(node, closestDist);
		}
	}
}

void randomGraph(TemplateVector<GraphNode> & nodes_out, int size, int width, int height, float dist)
{
	nodes_out.setSize(size);
	V2DF loc;
	for(int i = 0; i < nodes_out.size(); ++i)
	{
		bool unique;
		do
		{
			unique = true;
			int x = std::rand()%width;
			int y = std::rand()%height;
			loc.set(x,y);
			for(int a = 0; unique && a < nodes_out.size(); ++a)
			{
				unique = !nodes_out.get(a).pos.equals(loc);
			}
		}
		while(!unique);
		nodes_out.set(i, GraphNode((i%26)+'A', loc));
	}
	makeConnections(nodes_out, dist, true);
}

void printGraphData(TemplateVector<GraphNode> & nodes)
{
	GraphNode * node, * nodei, * nodec;
	int numConnections = 0;
	printf("GraphNode g_nodes[] = {\n");
	for(int n = 0; n < nodes.size(); ++n)
	{
		node = &nodes.get(n);
		printf("/*%2d*/GraphNode(\'%c\', XY(%d, %d)),\n", n, node->value, node->pos.x, node->pos.y);
		numConnections += node->edges.size();
	}
	printf("};\nint g_edges[%d] = {\n", numConnections*2);
	for(int n = 0; n < nodes.size(); ++n)
	{
		node = &nodes.get(n);
		for(int c = 0; c < node->edges.size(); ++c)
		{
			printf("%d,", n);
			nodec = node->edges.get(c).to;
			for(int i = 0; i < nodes.size(); ++i)
			{
				nodei = &nodes.get(i);
				if(nodei == nodec)
				{
					printf("%d", i);
					break;
				}
			}
			printf(",   ");
		}
		printf("\n");
	}
	printf("};");
}